/**
 * 85. 最大矩形
 * https://leetcode-cn.com/problems/maximal-rectangle/
 */

/**
 * @param {number} heights
 * @param {number[]} stack
 * @param {number[]} lefts
 * @param {number[]} rights
 * @return {number}
 */
function largestRectangleArea(heights, stack, lefts, rights) {
  const { length } = heights;
  let top = -1;
  for (let i = 0; i < length; i += 1) {
    const height = heights[i];
    while (top >= 0 && height <= heights[stack[top]]) {
      top -= 1;
    }
    lefts[i] = top >= 0 ? stack[top] : -1;
    top += 1;
    stack[top] = i;
  }
  top = length;
  for (let i = length - 1; i >= 0; i -= 1) {
    const height = heights[i];
    while (top < length && height <= heights[stack[top]]) {
      top += 1;
    }
    rights[i] = top < length ? stack[top] : length;
    top -= 1;
    stack[top] = i;
  }
  let max = 0;
  for (let i = 0; i < length; i += 1) {
    const area = heights[i] * ((i - lefts[i] - 1) + (rights[i] - i - 1) + 1);
    if (area > max) max = area;
  }
  return max;
}

/**
 * @param {string[][]} matrix
 * @return {number}
 */
function maximalRectangle(matrix) {
  const { length: n } = matrix;
  if (n === 0) return 0;
  const { length: m } = matrix[0];
  if (m === 0) return 0;
  const sign = new Array(n);
  for (let i = 0; i < n; i += 1) {
    sign[i] = new Array(m).fill(0);
  }
  for (let j = 0; j < m; j += 1) {
    let count = 0;
    for (let i = 0; i < n; i += 1) {
      if (matrix[i][j] === '1') {
        count += 1;
        sign[i][j] = count;
      } else {
        count = 0;
      }
    }
  }
  let max = 0;
  const lefts = new Array(m).fill(0);
  const rights = new Array(m).fill(0);
  const stack = new Array(m).fill(0);
  for (let i = 0; i < n; i += 1) {
    const area = largestRectangleArea(sign[i], stack, lefts, rights);
    if (area > max) max = area;
  }
  return max;
}

console.log(maximalRectangle([['1', '0', '1', '0', '0'], ['1', '0', '1', '1', '1'], ['1', '1', '1', '1', '1'], ['1', '0', '0', '1', '0']]) === 6);
console.log(maximalRectangle([]) === 0);
console.log(maximalRectangle([['0']]) === 0);
console.log(maximalRectangle([['1']]) === 1);
console.log(maximalRectangle([['0', '0']]) === 0);
